package dnaSequencer;

import java.util.ArrayList;

public class QuickSort<T extends Comparable<T>>
{
   public void sort(ArrayList<T> array)
   {
      array = quicksort(array, 0, array.size()-1);
   }
 
   private ArrayList<T> quicksort(ArrayList<T> array, int lo, int hi)
   {
      if (hi > lo)
      {
         int partitionPivotIndex = (int)(Math.random()*(hi-lo) + lo);
         int newPivotIndex = partition(array, lo, hi, partitionPivotIndex);
         quicksort(array, lo, newPivotIndex-1);
         quicksort(array, newPivotIndex+1, hi);
      }
      return (ArrayList<T>) array;
   }
 
   private int partition(ArrayList<T> array, int lo, int hi, int pivotIndex)
   {
      T pivotValue = array.get( pivotIndex );
 
      swap(array, pivotIndex, hi); //send to the back
 
      int index = lo;
 
      for (int i = lo; i < hi; i++)
      {
         if ( (array.get(i)).compareTo(pivotValue) <= 0 )
         {
            swap(array, i, index);
            index++;
         }
     }
 
      swap(array, hi, index);
 
      return index;
   }
 
   private void swap(ArrayList<T> array, int i, int j)
   {
      T temp = array.get(i);
      array.set(i, array.get(j));
      array.set(j, temp);
   }
 
}